package CyclicLinkedList;

public class DoublyCircularLinkedList {
    private static class Node {
        int data;
        Node prev;
        Node next;

        public Node(int data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }
    }

    private Node head;
    private int length;

    public DoublyCircularLinkedList() {
        head = null;
        length = 0;
    }

    // 头插法
    public void insertAtHead(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            head.next = head;
            head.prev = head;
        } else {
            Node tail = head.prev;
            newNode.next = head;
            newNode.prev = tail;
            head.prev = newNode;
            tail.next = newNode;
            head = newNode;
        }
        length++;
    }

    // 尾插法
    public void insertAtTail(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            head.next = head;
            head.prev = head;
        } else {
            Node tail = head.prev;
            newNode.next = head;
            newNode.prev = tail;
            tail.next = newNode;
            head.prev = newNode;
        }
        length++;
    }

    // 删除节点
    public boolean deleteNode(int data) {
        if (head == null) return false;

        Node current = head;

        do {
            if (current.data == data) {
                if (current == head) {
                    if (head.next == head) {
                        head = null;
                    } else {
                        Node tail = head.prev;
                        head = head.next;
                        head.prev = tail;
                        tail.next = head;
                    }
                } else {
                    current.prev.next = current.next;
                    current.next.prev = current.prev;
                }
                length--;
                return true;
            }
            current = current.next;
        } while (current != head);

        return false;
    }

    // 反转链表
    public void reverse() {
        if (head == null || head.next == head) return;

        Node current = head;
        Node temp = null;

        do {
            // 交换prev和next指针
            temp = current.prev;
            current.prev = current.next;
            current.next = temp;
            current = current.prev; // 因为已经交换了prev和next，所以这里用prev
        } while (current != head);

        // 更新头节点
        head = head.next;
    }

    // 打印链表
    public void display() {
        if (head == null) {
            System.out.println("链表为空");
            return;
        }

        Node temp = head;
        do {
            System.out.print(temp.data);
            if (temp.next != head) {
                System.out.print(", ");
            }
            temp = temp.next;
        } while (temp != head);
        System.out.println();
    }

    public int getLength() {
        return length;
    }
}